import numpy


# r : 五个设备
# c : 七个动作
# 求覆盖所有的动作的最小权值
result = [-1, -1, -1, -1, -1, -1, -1]
device = numpy.array([0, 1, 2, 3, 4])
action = numpy.array([0, 1, 2, 3, 4, 5, 6])
def min_index(matrix, weight):
    average_weight = []
    del_rows = []
    for i in range(len(matrix)):
        count = sum(matrix[i])
        if count == 0:
            del_rows.append(i)
    if len(del_rows) != 0:
        matrix = numpy.delete(matrix, del_rows, 0)
        weight = numpy.delete(weight, del_rows)
        global device
        device = numpy.delete(device, del_rows)
    for i in range(len(matrix)):
        count = sum(matrix[i])
        average_weight.append(float(weight[i]) / count)
    if len(average_weight) == 0:
        return -1
    index = average_weight.index(min(average_weight))
    return index, matrix, weight

def modify_matrix(matrix, index, weight):
    del_index = []
    global action
    for i in range(len(matrix[index])):
        if matrix[index][i] == 1:
            del_index.append(i)
    matrix = numpy.delete(matrix, del_index, 1)
    matrix = numpy.delete(matrix, index, 0)
    for d_i in del_index:
        if result[action[d_i]] == -1:
            result[action[d_i]] = index
    global device
    device = numpy.delete(device, index)
    action = numpy.delete(action, del_index)
    weight = numpy.delete(weight, index)
    return matrix, weight

def get_min_collection(matrix, weight):
    while matrix.size != 0:
        while contains_unique(matrix):
            matrix, weight = get_unique_collection(matrix, weight)
        if matrix.size == 0:
            return
        index, matrix, weight = min_index(matrix, weight)
        result.append(device[index])
        matrix, weight = modify_matrix(matrix, index, weight)

def get_unique_collection(matrix, weight):
    unique_device = set()
    del_c = set()
    global device
    global action
    for c in range(len(matrix[0])):
        count = 0
        row = -1
        for r in range(len(matrix)):
            count += matrix[r][c]
            if matrix[r][c] == 1:
                row = r
        if count == 1:
            unique_device.add(row)
    for r in unique_device:
        for c in range(len(matrix[0])):
            if matrix[r][c] == 1 and result[action[c]] == -1:
                del_c.add(c)
                result[action[c]] = device[r]
    unique_device = list(unique_device)
    del_c = list(del_c)
    # for re in unique_device:
    #     result.append(re)
    matrix = numpy.delete(matrix, unique_device, 0)
    matrix = numpy.delete(matrix, del_c, 1)

    device = numpy.delete(device, unique_device)
    action = numpy.delete(action, del_c)
    weight = numpy.delete(weight, unique_device)
    return matrix, weight


def contains_unique(matrix):
    for column in range(len(matrix[0])):
        count = 0
        for row in range(len(matrix)):
            count += matrix[row][column]
        if count == 1:
            return True
    return False


if __name__ == '__main__':
    matrix = [[1, 0, 0, 0, 0, 0, 1],
              [1, 0, 1, 1, 0, 1, 0],
              [0, 1, 0, 1, 1, 0, 0],
              [1, 1, 1, 0, 1, 0, 0],
              [0, 0, 1, 0, 0, 1, 1]]
    matrix = numpy.array(matrix)
    weight = [0.6, 0.4, 0.2, 0.9, 0.6]
    weight = numpy.array(weight)
    get_min_collection(matrix, weight)
    print(result)

